package bank;

import java.util.*;

public class _30FindSubstring {
    public static List<Integer> findSubstring(String s, String[] words) {
        //  尝试回溯法
        //  该算法在力扣运行超时！！！
        HashSet<Integer> res = new HashSet<>();
        backtrack(s,words,res,new HashSet<Integer>(),new StringBuilder());
        return new ArrayList<>(res);
    }

    private static void backtrack(String s, String[] words, HashSet<Integer> res, HashSet<Integer> hashSet, StringBuilder stringBuilder) {
        //  终止条件
        if (stringBuilder.length() == words.length*words[0].length()){
            //  存放结果
            //  需要注意的是indexOf()方法只返回第一次出现的下标
            for (int i = 0;i <= s.length();i++){
                if (s.substring(i).startsWith(stringBuilder.toString())){
                    res.add(i);
                }
            }
            return;
        }
        //  遍历words
        for (int i = 0;i < words.length;i++){
            if (!hashSet.contains(i)){
                //  需要注意的是words中有相同的word的情况
                hashSet.add(i);
                stringBuilder.append(words[i]);
                backtrack(s,words,res,hashSet,stringBuilder);
                hashSet.remove(i);
                stringBuilder.delete(stringBuilder.length()-words[i].length(),stringBuilder.length());
            }
        }
    }
}
